Distributed software applications may comprise multiple concurrent and often autonomous processes, communicating with one another and/or with shared resources across one or more networks. For example, a distributed storage service may include multiple concurrent processes executing across a distributed hardware infrastructure, such as one or more clusters of computers. Various ones of these processes may be executing on different physical and/or logical (e.g., virtual) machines in the cluster(s). In a storage service, for example, processes (e.g., software servers) on different machines may each expose a programmatic interface to clients, which the clients may use to access a single, virtual file system that may be implemented across multiple storage resources. The storage service may store multiple replicas of each data item in the system, such that any change to a data item on one server must be propagated to one or more other servers.
In a distributed storage system in which multiple clients can update stored data, the data received from the system may always be considered “stale”. For example, by the time one client receives a response to a request to read a data item from one of the servers, another client may have already updated the data item on another one of the servers. In such systems, it may be useful for the client to know just how stale its data is, i.e., approximately how long it has been since any data read by the client was known to be valid. Some existing systems use a heartbeat protocol to determine the staleness of a client machine and a separate transaction protocol to effect and propagate changes in the stored data or the shared state of the system on various servers in the system. Synchronizing these processes can be complex and error-prone, and does not result in a method for computing and tracking the staleness of any particular data items in a meaningful way.
While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that the embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.